package com.zrf.base.knowledge.leetcode.editor.cn;

/**
 * //给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 * //
 * // 示例：
 * //
 * // 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * //
 * //当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * //
 * //
 * // 说明：
 * //
 * // 给定的 n 保证是有效的。
 * //
 * // 进阶：
 * //
 * // 你能尝试使用一趟扫描实现吗？
 * // Related Topics 链表 双指针
 * // 👍 1084 👎 0
 *
 * @author zhouruifeng
 * @date 2020-10-24 18:11:50
 */
public class RemoveNthNodeFromEndOfList {
    public static void main(String[] args) {
        RemoveNthNodeFromEndOfList removeNthNodeFromEndOfList = new RemoveNthNodeFromEndOfList();
        Solution solution = removeNthNodeFromEndOfList.new Solution();
        ListNode listNode = removeNthNodeFromEndOfList.new ListNode(1, removeNthNodeFromEndOfList.new ListNode(2));
//        listNode.next = new RemoveNthNodeFromEndOfList().new ListNode(2);
//        listNode.next.next = new RemoveNthNodeFromEndOfList().new ListNode(3);
//        listNode.next.next.next = new RemoveNthNodeFromEndOfList().new ListNode(4);
//        listNode.next.next.next.next = new RemoveNthNodeFromEndOfList().new ListNode(5);
        System.out.println(solution.removeNthFromEnd(listNode, 1));
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode listNode = new ListNode(0, head);
            ListNode first = listNode;
            ListNode second = head;
            for (int i = 0; i < n; i++) {
                second = second.next;
            }

            while (second != null) {
                first = first.next;
                second = second.next;
            }

            first.next = first.next.next;

            return listNode.next;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}